Portable communication devices such as mobile telephones, personal digital assistants (PDAs) and “wearable” computers generally have limited computational resources in terms of one or more factors such as memory, processing power, communication bandwidth and network connection time. Such devices are therefore referred to herein as “lightweight” devices. Although lightweight devices are increasingly being used for sending and retrieving information over the Internet, their limited resources can become problematic for certain applications, such as electronic commerce, that require the use of digital signatures. More specifically, the computational requirements associated with many well-known digital signature protocols can prevent effective implementation of such protocols in lightweight devices. By way of example, it can take about thirty seconds to perform one simple modular exponentiation on a processor of the type that is common in mobile telephones and PDAs. Increasing the processor speed will cause a faster battery drain or require bulkier batteries, neither of which is desirable.
While there are conventional signature protocols, such as Merkle and Lamport signatures, that are well suited for lightweight device applications, these signatures are generally incompatible with existing and proposed public-key infrastructures (PKIs).
There are also a number of substantial security risks associated with the generation of digital signatures on lightweight devices using conventional techniques. One such risk arises from theft of the device itself. In such a situation, the thief may be able to produce signatures in the name of the victim of the theft.
Another problem is the potential for “bait-and-switch” attacks that may be implemented by viruses or other mechanisms. For example, a virus could be configured to prompt a user of a lightweight device to sign an innocuous message presented on a display of the device, and after the user agrees to sign, to replace that message with a different message on which the signature is generated. Once this signature has been generated, the user has in principle agreed to any corresponding contract terms, whatever they may be.
Another related attack is one in which a virus is configured to bypass a stage at which user consent is requested, so as to cause a digital signature to be generated on a message without user consent.
It is also possible that a secret key of the user may be compromised by a virus or other mechanism, such that an attacker is thereby permitted to generate signatures on arbitrary messages produced by the user.
These security risks create a danger that users may be held to have entered contracts that they never intended to enter. On the other hand, there is also a significant danger for digital signature recipients that a purported signer can later argue that he or she did not generate the signature. This latter situation is referred to as signature repudiation. As a result of these and other problems, utilization of digital signatures in electronic commerce and other important applications may be unduly limited.
Although it is known in the art to revoke public keys in order to combat one or more of the above-identified problems, there are generally no effective techniques available that allow for revocation of particular digital signatures. A revoked public key means that any signatures known to have been generated using the corresponding secret key after the revocation are considered invalid, while signatures known to have been generated before the revocation are considered valid.
However, a problem arises with those signatures that are claimed to have been generated before revocation, but which in actuality are not. Existing public key revocation techniques are inadequate in these and other respects.
A need therefore exists in the art for improved techniques for generating digital signatures, so as to overcome the security risks and signature repudiation problem identified above, while also being computationally efficient so as to permit implementation in mobile telephones, PDAs, wearable computers and other lightweight devices.